// Given nums = [2, 7, 11, 15], target = 9,
// Because nums[0] + nums[1] = 2 + 7 = 9,
// return [0, 1].

//数据结构：哈希表
//时间复杂度： O(nlogn)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  var pairs = [];
  for (var i = 0; i < nums.length; i++) {
    pairs[i] = new Pair(nums[i], i);
  }
  pairs = bubbleSort(pairs);
  var left = 0;
  var right = nums.length - 1;
  var sum = 0;
  while (left < right) {
    sum = pairs[left].value + pairs[right].value;
    if (sum == target) {
      var returnNums = [];
      returnNums[0] = pairs[left].index;
      returnNums[1] = pairs[right].index;
      if (returnNums[0] > returnNums[1]) {
        var m = returnNums[0];
        returnNums[0] = returnNums[1];
        returnNums[1] = m;
      }
      return returnNums;
    } else if (sum > target) {
      right--;
    } else if (sum < target) {
      left++;
    }
  }
  throw new Error('没有结果');
}

/**
 * @param {[numbers]} value [值]
 * @param {[numbers]} index [索引]
 */
function Pair(value, index) {
  this.value = value;
  this.index = index;
}

/**
 * 根据Pair值进行冒泡排序
 * @param  {[type]} array [description]
 * @return {[type]}       [description]
 */
function bubbleSort(array) {
  var length = array.length;
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length; j++) {
      if (array[i].value < array[j].value) {
        var m = array[i];
        array[i] = array[j];
        array[j] = m;
      }
    }
  }
  return array;
}

console.log(twoSum([1, 4, 2, 5, 8], 6));
